\documentclass{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
%\usepackage{ctex}
\usepackage{listings}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\usepackage{xcolor}
\usepackage{fontspec} 
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{comment}{rgb}{0.56,0.64,0.68}

\newfontfamily\monaco{Monaco}
\lstset {
aboveskip=3mm,
belowskip=3mm,
showstringspaces=false,       % underline spaces within strings
columns=flexible,
framerule=1pt,
rulecolor=\color{gray!35},
backgroundcolor=\color{gray!5},
basicstyle={\small\monaco},           % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\tiny\monaco\color{gray},  % the style that is used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
commentstyle=\color{comment},
keywordstyle=\color{blue},
stringstyle=\color{dkgreen},
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
escapeinside={\%*}{*)},            % if add LaTeX within your code
morekeywords={*,...}               % if add more keywords to the set
}


\begin{document}
\title{Homework \#1}
\pagestyle{fancy}
\lhead{Name Li HuiTeng 3180102114}
\chead{ numPDE\#1}
\rhead{Date 20.04.01}

\section*{7.9 Verify that (7.7) is indeed a norm.}
  \begin{proof}[Proof]
	Since Real Positivity and Point Separation are obvious, 
	we only need to show that Absolute Homogeneity and Triangle Inequality hold.

	For Absolute Homogeneity, the result is immediate if $a=0$. We have
		\begin{align*}
		 \forall a \in \mathbb{F}  (a\neq 0),T \in \mathcal{L} (\mathbb{F}^n,\mathbb{F}^m),
		 \|aT\| &=\inf \{M: \forall x \in {\mathbb{F}}^{n},|aTx|\leq M|x|\} \\
				&=\inf \{M: \forall x \in {\mathbb{F}}^{n},|Tx|\leq \frac{M|x|}{|a|}\} \\
				&=\inf \{|a|\cdot M: \forall x \in {\mathbb{F}}^{n},|Tx|\leq M|x|\} \\
				&=|a|\cdot \|T\|
		\end{align*}
	For Triangle Inequality, we have
	\begin{align*}
		\forall x \in \mathbb{F}^n, T_1,T_2 \in \mathcal{L} (\mathbb{F}^n,\mathbb{F}^m),
		|(T_1+T_2)(x)| =|T_1x+T_2x| 
		&\leq |T_1(x)|+|T_2(x)| \\
		&\leq \|T_1\|\cdot|x|+\|T_2\|\cdot|x|\\
		&=(\|T_1\|+\|T_2\|)\cdot|x|
	 \end{align*}
	Thus, $\|T_1+T_2\| \leq \|T_1\|+\|T_2\|.$
  \end{proof}

  \section*{7.14 Verify that (7.7) induces a metric space with $d(T,S):=\|T-S\|$.}
  \begin{proof}[Proof]
	 This follows from 7.9 directly.(Just a trivial check on Real Positivity, Point separation, Symmetry and Triangle Inequality.)
  \end{proof}

  \section*{7.15 }
  \begin{proof}[Proof]
	The first problem is a bit confusing. If L:$R^n \to C^m$, there's no doubt that L actually maps $R^n$ to $R^m$ since 
	every element in Range(L) can be expressed in linear combination of $L(e_i)$ with 
	coefficients in R. (However, if L:$C^n \to C^m$, the suppose won't hold any more. Just consider $T(i\cdot e_k)=i\cdot T(e_k)$.) (Unless T=0) 

	The second problem is to prove if T:$R^n\to R^m$ expands to $C^n\to C^m$, the norm of T will 
	remain unchanged. Let $SupR=\sup_{x \in R^n;|x| \leq 1}|Tx|=\sup_{x \in R^n;|x| = 1}|Tx|,SupC=\sup_{x \in C^n;|x| \leq 1}|Tx|=\sup_{x \in C^n;|x|=1}|Tx|$.

	On one side, obviously $SupR \leq SupC$.

	On the other side,   
	for any X $\in C^n and|X|=1$, X can be uniquely expressed in
	\[X=Y+iZ\]with
	\[Y,Z \in R^n;	|Y|^2+|Z|^2=1\]
	If we could pick some X so that |T(X)| > SupR holds, Y and Z should be non-zero. 
	Also, since Range(T) is contained in $R^m$, we have   
	\[|T(X)|^2=|T(Y)+iT(Z)|^2=|T(Y)|^2+|T(Z)|^2 = |Y|^2|T(Y/|Y|)|^2+|Z|^2|T(Z/|Z|)|^2 
	\leq |Y|^2SupR^2 + |Z|^2SupR^2=SupR^2,\]
	because $Y/|Y|,Z/|Z| \in R^n$ with their norm =1. A contradiction!

	Hence for any $X\in C^n,|X|=1$, we have $|T(x)| \leq SupR$. This implies $SupC\leq SupR$, i.e. SupC=SupR.  


  \end{proof}

  \section*{7.17 Verify that (7.10) is indeed a norm.}
  \begin{proof}[Proof]
	Since Real Positivity and Point separation are obvious, 
	we again need to show that Absolute Homogeneity and Triangle Inequality hold.

	For Absolute Homogeneity, the result is immediate if $a=0$. We have
		\begin{align*}
		 \forall a \in \mathbb{F}  (a\neq 0),T \in \mathcal{L} (\mathbb{F}^n,\mathbb{F}^m),
		 |aT|^2 
		&=\sum_{j = 1}^{n}{|aT(e_j)|}^2\\
		&=\sum_{j = 1}^{n}{|a|^2\cdot|T(e_j)|}^2\\
		&=|a|^2\cdot\sum_{j = 1}^{n}{|T(e_j)|}^2\\
		&=|a|^2\cdot |T|^2
		\end{align*}
	For Triangle Inequality, we have
	\begin{align*}
		\forall T_1,T_2 \in \mathcal{L} (\mathbb{F}^n,\mathbb{F}^m),
		|T_1+T_2|^2 
		&=\sum_{j = 1}^{n}{|(T_1+T_2)(e_j)|}^2\\
		&=\sum_{j = 1}^{n}{(|T_1(e_j)|^2+|T_2(e_j)|^2+2|T_1(e_j)||T_2(e_j)|)}\\
		&=|T_1|^2+|T_2|^2+\sum_{j = 1}^{n}{(2|T_1(e_j)||T_2(e_j)|)}\\
		(H\ddot{o}lder\quad Inequality) &\leq |T_1|^2+|T_2|^2+2(\sum_{j = 1}^{n}{|T_1(e_j)|^2})^{\frac{1}{2}}\cdot (\sum_{j = 1}^{n}{|T_2(e_j)|^2})^{\frac{1}{2}} \\
		&=|T_1|^2+|T_2|^2+2|T_1||T_2|\\
		&=(|T_1|+|T_2|)^2.
	 \end{align*}
	Thus, $|T_1+T_2| \leq |T_1|+|T_2|.$
\end{proof}

\section*{7.21 Prove $|ST| \leq |T||S|$.}
\begin{proof}[Proof]
  By Corollary 7.19, we have
  \begin{align*}
	  \forall x \in \mathbb{F}^n,T\in \mathcal{L} (\mathbb{F}^n,\mathbb{F}^m), S\in \mathcal{L} (\mathbb{F}^m,\mathbb{F}^k),\\
	  |S\cdot T|^2 
	  &=\sum_{j = 1}^{n}{|S(Te_j)|}^2\\
	  &\leq\sum_{j = 1}^{n}{|S|^2|Te_j|^2}\\
	  &=|S|^2\cdot\sum_{j = 1}^{n}{|Te_j|^2}\\
	  &=|S|^2\cdot|T|^2.
   \end{align*}
  Thus, $|S\cdot T| \leq |S|\cdot|T|.$
\end{proof}

\section*{7.38 Prove Theorem 7.37.}
\begin{proof}[Proof]
  This will follow directly from Corollary 7.36 if X is diagonalizable. 
  If X is not diagonalizable, by using Schur Theorem, 
  we have a nonsingular matrix U (in fact U is unitary) so that $X=U\Lambda U^{-1}$, 
  where $\Lambda$ is upper triangular and the diagonal entries are just the eigenvalues of X. 
  
  Notice several facts as follows.
  \begin{itemize}
	\item[1.]$e^{\Lambda }$ is upper triangular since the sum and the product of upper triangular 
  matrices are still upper triangular.   
	\item[2.]The entries of $e^{\Lambda }$ are $e^{\lambda_1},\cdots,e^{\lambda_n}$, 
	where $\lambda_1,\cdots,\lambda_n$ are roots of X's characteristic polynomial.
	\item[3.]The determinant of an upper triangular matrix is the product of all entries.
	\item[4.]The trace of a matrix is the sum of all eigenvalues (including multiple roots). 
  \end{itemize}
  
  Thus, $det(e^X)=det(e^{\Lambda })=e^{\lambda_1}\cdot e^{\lambda_2}\cdot \cdots e^{\lambda_n}=e^{\sum \lambda_i}=e^{Trace X}.$
\end{proof}



\section*{7.57 Calculate det(M) with $M_{s\times s}$.}
\begin{proof}[Proof]
 The proof is by mathematical induction on s. 
 The result is immediate if $s=1$. 
 Assume that for some integer $s \geq 2$ 
 the determinant of $(s-1)\times(s-1)$ matrix satisfies the equation. 
 By expanding along the s-th column, we have
	 \begin{align*}
	 det(M_{s\times s})&=(-1)\cdot(-1)^{2s-1}\cdot 
	 \left|\begin{array}{cccccc}
		z &-1&  & &\\ 
		 &z& -1 & &\\
		 &	& \ddots& \ddots&\ddots\\  
		 &  & & z& -1\\
		\alpha_0 &\alpha _1 &\cdots &\cdots & \alpha_{s-2}
	\end{array}\right|  \\ 
	&+ (-1)^{2s}\cdot z^{s-1}\cdot(z+\alpha_{s-1})\\
	&=det(M_{(s-1)\times(s-1)})+
	\left|\begin{array}{cccccc}
		z &-1&  & &\\ 
		 &z& -1 & &\\
		 &	& \ddots& \ddots&\ddots\\  
		 &  & & z& 0\\
		\alpha_0 &\alpha _1 &\cdots &\cdots & -z
	\end{array}\right|_{(s-1)\times(s-1)} \\
	&+z^{s-1}\cdot (z+\alpha_{s-1})\\
	&=z^{s-1}+\sum_{n = 1}^{s-2}\alpha_n z^n - z^{s-1}+z^{s-1}\cdot (z+\alpha_{s-1})\\
	&=z^{s}+\sum_{n = 1}^{s-1}\alpha_n z^n
  \end{align*}
This shows the theorem is true for $n=s$, and so the theorem is true for all square 
matrices by mathematical induction.
\end{proof}

\section*{7.110 Compute $C_j$ of the trapezoidal rule and the midpoint rule.}
\begin{proof}[Proof]
By using (7.68), we compute by Matlab.

\lstset{language=Matlab}
\begin{lstlisting}
%This is a file named test_compute.m .

	a_trape=[-1 1];
	b_trape=[0.5 0.5];
	
	a_midpoint=[-1 0 1];
	b_midpoint=[0 2 0];
	
	a_euler=[-1 1];
	b_euler=[1 0];
	
	format rat;
	C_j=Compute_C_j(a_euler,b_euler)    %compare it with Example 7.109
	C_j_midpoint=Compute_C_j(a_midpoint,b_midpoint)
	C_j_trapezoidal=Compute_C_j(a_trape,b_trape)

%This is a file named Compute_C_j.m .

	function y=Compute_C_j(a,b)
    s=length(a)-1;
    y=zeros(5,1);
    y(1,1)=sum(a);
    for i=1:4
        for m=0:s
            y(i+1,1)=y(i+1,1)+a(m+1)*(m^i)/factorial(i)-(b(m+1)*(m^(i-1))/factorial(i-1));
        end
    end
end	

%This is the input and the output of Terminal. (The comments are added to imply answers)
	>> test_Compute

	C_j =
	
		   0       
		   0       
		   1/2     
		   1/6     
		   1/24    
	
	
	C_j_midpoint =
	
		   0	  %C_0 of midpoint rule       
		   0    %C_1 of midpoint rule    
		   0    %C_2 of midpoint rule    
		   1/3     %C_3 of midpoint rule 
		   1/3     %C_4 of midpoint rule 
	
	
	C_j_trapezoidal =
	
		   0    %C_0 of trapezoidal rule    
		   0    %C_1 of trapezoidal rule   
		   0    %C_2 of trapezoidal rule   
		  -1/12    %C_3 of trapezoidal rule
		  -1/24    %C_4 of trapezoidal rule
\end{lstlisting}
C-j agrees with Example 7.109, which makes the output convincing. 
\end{proof}

\section*{7.112 Express conditions of $\mathcal{L}=\mathcal{O}(k^{3})$ by using characteristic polynomials.}
\begin{proof}[Proof]
Similar to Example 7.111, the conditions are 
	\begin{itemize}
		\item[1.]$\rho(1)=0 $  
		\item[2.]$\rho^{'}(1)=\sigma(1) $
		\item[3.]$\rho^{''}(1)+\rho^{'}(1)=2\sigma^{'}(1)$
	\end{itemize}  
\end{proof}


\section*{7.113 Derive coefficients of ABF, AMF, BDF by using symbolic computation.}
\begin{proof}[Proof]
The MatLab codes are included in a file named 7.113.tar. By entering two inputArgs, we can quickly check 
whether the given pair (s,p) in the given LMM constructs a well-posed problem or not, and 
further derive the coefficients which satisfies demands of 7.113.

You can choose three different functions: Coeffi-AB(),Coeffi-AM(), 
and Coeffi-BDF(), with two positive integer inputArgs.

The first inputArg represents step 's', 
and the next inputArg represents our expected order of accuracy 'p'.
\begin{itemize}
	\item[1.]If the pair (s,p) constructs a well-posed equation set, 
the function will return a STRUCT with coefficients as members.
	\item[2.]If 'p' cannot be reached in 's' steps,
the function will return a STRUCT with 'Empty sym: 0-by-1' as members. 
	\item[3.]If 's' is redundant for 'p', 
the function will return a STRUCT with a system of fundamental solutions.
\end{itemize}
The codes of three functions will be shown below.
\lstset{language=Matlab}
\begin{lstlisting}
%This is a file named Coeffi_AB.m .
function AB= Coeffi_AB(s,p)
a= sym('a',[1 s+1]);
b= sym('b',[1 s+1]);

%AB_a
for i=1:s-1
    a(i)=0;
end
a(s)=-1;
a(s+1)=1;

%AB_b
b(s+1)=0;

equ(1)=sum(a);

 for i=1:p
     equ(i+1)=0;
        for m=0:s
            equ(i+1)=equ(i+1)+a(m+1)*(m^i)/factorial(i)-(b(m+1)*(m^(i-1))/factorial(i-1));
        end
     condition(i)= equ(i+1)==0;
 end
 
AB=solve(condition);
end

%This is a file named Coeffi_AM.m .
function AM= Coeffi_AM(s,p)
a= sym('a',[1 s+1]);
b= sym('b',[1 s+1]);

%AM_a
for i=1:s-1
    a(i)=0;
end
a(s)=-1;
a(s+1)=1;

equ(1)=sum(a);

 for i=1:p
     equ(i+1)=0;
        for m=0:s
            equ(i+1)=equ(i+1)+a(m+1)*(m^i)/factorial(i)-(b(m+1)*(m^(i-1))/factorial(i-1));
        end
     condition(i)= equ(i+1)==0;
 end
 
AM=solve(condition);
end

%This is a file named Coeffi_BDF.m .
function BDF= Coeffi_BDF(s,p)
a= sym('a',[1 s+1]);
b= sym('b',[1 s+1]);

%AB_a
a(s+1)=1;

%AB_b
for i=1:s
    b(i)=0;
end

equ(1)=sum(a);
condition(1)= equ(1)==0;
 for i=1:p
     equ(i+1)=0;
        for m=0:s
            equ(i+1)=equ(i+1)+a(m+1)*(m^i)/factorial(i)-(b(m+1)*(m^(i-1))/factorial(i-1));
        end
     condition(i+1)= equ(i+1)==0;
 end
 
BDF=solve(condition);
end

\end{lstlisting}

An example will be shown below, along with the answer 
which is saved as "-Coeffi-result.mat". 

(A copy of my latex document and matlab data has been sent by email.)
\lstset{language=Matlab}
\begin{lstlisting}
clear
clc
AB_test_'0-1'=Coeffi_AB(2,4)  %condition:'p' cannot be reached in 's' steps 
AM_test_wellposed=Coeffi_AM(1,2)  %condition:well-posed
BDF_test_redundant=Coeffi_BDF(6,3)    %condition:redundant

%Check the result
clear
clc
AB1=Coeffi_AB(1,1);
AB2=Coeffi_AB(2,2);
AB3=Coeffi_AB(3,3);
AB4=Coeffi_AB(4,4);

AM1=Coeffi_AM(1,1);
AM2=Coeffi_AM(1,2);
AM3=Coeffi_AM(2,3);
AM4=Coeffi_AM(3,4);  
AM5=Coeffi_AM(4,5);

BDF1=Coeffi_BDF(1,1);
BDF2=Coeffi_BDF(2,2);
BDF3=Coeffi_BDF(3,3);
BDF4=Coeffi_BDF(4,4);
save('_Coeffi_result.mat');
\end{lstlisting}
\end{proof}


\section*{7.118 Derive the characteristic polynomials of 3rd BDF and verify the order of accuracy.}
\begin{proof}[Proof]
\[\rho(z)=z^3-\frac{18}{11}z^2+\frac{9}{11}z-\frac{2}{11},\] 
\[\sigma(z)=\frac{6}{11}z^3.\]
Hence 
\[
	\frac{\rho(z)}{\sigma(z)}-log(z)=\frac{11z^3-18z^2+9z-2-6z^3log(z)}{6z^3}
\]
Use Taylor Expansion at z=1 separately:
\begin{align*}
	11z^3-18z^2+9z-2&=0+6(z-1)+15(z-1)^2+11(z-1)^3,\\
	z^3log(z)&=0+1(z-1)+5/2(z-1)^2+11/6(z-1)^3+6/24(z-1)^4+\mathcal{O}((z-1)^5). 
\end{align*}
Thus when $z \to 1$, we have
\[
	\frac{\rho(z)}{\sigma(z)}-log(z)
	=\frac{-3/2(z-1)^4+\mathcal{O}((z-1)^5)}{6z^3}
	=\Theta ((z-1)^4),z\to 1 	
\]
It confirms that the 3rd BDF has order 3 with error constant $-\frac{1}{4}$.
\end{proof}


\section*{7.119 Prove an s-step LMM has order of p iff when applied to an ODE $u_t=q(t)$, 
it gives exact results whenever q is a polynomial of degree $\leq p-1$ , but not whenever q is a polynomial of degree p.}
\begin{proof}[Proof]
We prove a lemma at first: an s-step LMM has order at least p iff when applied to an ODE $u_t=q(t)$, 
it gives exact results whenever q is a polynomial of degree $\leq p-1$. 

On one side, we have $\forall i \leq p, C_i =0 $ since LMM has order at least p. 
Also, when $u_t=q(t)$ is a polynomial of degree less than p, we have $\forall i \geq p+1, u^{(i)} =0 $. 
Hence
\[\mathcal{L}(u)=\sum_{i=0}^{\infty}C_iu^{(i)}=
\sum_{i=0}^{p}0\cdot u^{(i)}+\sum_{i=p+1}^{\infty}C_i\cdot 0 =0\] 
Consider numerical initial data is exact, so the solution error equals zero.

On the other side, suppose an LMM has order q less than p, i.e. q+1 $\geq$ p. 
Thus $C_{q+1} \neq 0 $. Choose $u_t=q(t)=t^{q}$ with initial value $u_0(0)=1$. 
Then
\[\mathcal{L}(u)=\sum_{i=0}^{\infty}C_iu^{(i)}=
\sum_{i=0}^{q}0\cdot u^{(i)}+\sum_{i=q+2}^{\infty}C_i\cdot 0 +C_{q+1}\cdot q!
=C_{q+1}\cdot q! \neq 0\]
Then the solution error will incline to infinity. The solution is not even bounded, let alone exactness!  

Having completed the proof of the lemma, we come back to this theorem. The lemma proves part of the theorem and we will complete the remain. 

On one side, for an s-step LMM has order of p, supposing that it also gives exact results whenever q is a polynomial of degree $\leq p$, 
according to the lemma it must have order at least (p+1). A contradiction!

On the other side, if an LMM gives exact results whenever q is a polynomial of degree $\leq p-1$ , but not whenever q is a polynomial of degree p, 
by the lemma we see that it has order at least p but no more than p, which implies it has order of p.


\end{proof}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
